import java.util.ArrayList;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;


public class Expression {
	
	private static final boolean DEBUG = false;

	// this is an exhaustive list of expression types
	public static final String[] validTypes = {"plus", "minus", "times", 
		"divided by",  "or", "and", "not", "literal string", "literal float",
		"literal int", "identifier", "unary minus",
		"sum", "avg", "equals", "greater than", "less than"};

	// this is an exhaustive list of the unary expression types
	public static final String[] unaryTypes = {"not", "unary minus", "sum", "avg"};

	// this is an exhaustive list of the binary expression types
	public static final String[] binaryTypes = {"plus", "minus", "times",
		"divided by", "or", "and", "equals", "greater than", "less than"};

	// this is an exhaustive list of the value types
	// JES - maybe this should be static
	public static final String[] valueTypes = {"literal string", "literal float",
			"literal int", "identifier"};
	
	// These are the valid data types for an expression.
	public final int TYPE_BOOLEAN = 1;
	public final int TYPE_NUMERIC = 2;
	public final int TYPE_STRING = 3;
	
	public final int TYPE_MIN = 1;
	public final int TYPE_MAX = 3;

	// this is the type of the expression
	private String myType;

	// this is the literal value contained in the expression; only non-null
	// if myType is "literal" or "identifier"
	private String myValue;

	// these are the two subexpressions
	private Expression leftSubexpression;
	private Expression rightSubexpression;

	// prints the expression
	public String print() {

		String toMe;

		// see if it is a literal type
		for (int i = 0; i < valueTypes.length; i++) {
			if (myType.equals(valueTypes[i])) {
				toMe = myValue;
				return toMe;
			} 
		}

		// see if it is a unary type
		for (int i = 0; i < unaryTypes.length; i++) {
			if (myType.equals(unaryTypes[i])) {
				toMe = "(" + myType + " " + leftSubexpression.print () + ")";
				return toMe;
			}
		}

		// lastly, do a binary type
		for (int i = 0; i < binaryTypes.length; i++) {
			if (myType.equals(binaryTypes[i])) {
				toMe = "(" + leftSubexpression.print () + " " + myType + " " + rightSubexpression.print () + ")";
				return toMe;
			}
		}
		
		throw new RuntimeException("got a bad type in the expression when printing");
	}

	// create a new expression of type specified type
	public Expression(String expressionType) {

		// verify it is a valid expression type
		for (int i = 0; i < validTypes.length; i++) {
			if (expressionType.equals (validTypes[i])) {
				myType = expressionType;
				return;
			}
		}

		// it is not valid, so throw an exception
		throw new RuntimeException ("you tried to create an invalid expr type \"" + expressionType + "\".");
	}

	public String getType() {
		return myType;
	}

	// this returns the value of the expression, if it is a literal (in which
	// case the literal value encoded as a string is returned), or it is an
	// identifier (in which case the name of the identifier is returned)
	public String getValue () {
		for (int i = 0; i < valueTypes.length; i++) {
			if (myType.equals (valueTypes[i])) {
				return myValue;
			}
		}
		
		throw new RuntimeException ("you can't get a value for that expr type!");
	}

	// this sets the value of the expression, if it is a literal or an 
	// identifier
	public void setValue (String toMe) {
		for (int i = 0; i < valueTypes.length; i++) {
			if (myType.equals (valueTypes[i])) {
				myValue = toMe;
				return;
			}
		} 
		throw new RuntimeException ("you can't set a value for that expr type!");
	}

	// this gets the subexpression, which is only possible if this is a 
	// unary operation (such as "unary minus" or "not")
	public Expression getSubexpression () {

		// verify it is a valid expression type
		for (int i = 0; i < unaryTypes.length; i++) {
			if (myType.equals (unaryTypes[i])) {
				return leftSubexpression;
			}
		}

		// it is not valid, so throw an exception
		throw new RuntimeException ("you can't get the subexpression of an " +
				"expression that is not unary!");
	}

	// this sets the subexpression, which is only possible if this is a 
	// unary operation (such as "unary minus" or "not")
	public void setSubexpression (Expression newChild) {

		// verify it is a valid expression type
		for (int i = 0; i < unaryTypes.length; i++) {
			if (myType.equals (unaryTypes[i])) {
				leftSubexpression = newChild;
				return;
			}
		}

		// it is not valid, so throw an exception
		throw new RuntimeException ("you can't set the subexpression of an " +
				"expression that is not unary!");
	}

	// this gets either the left or the right subexpression, which is only 
	// possible if this is a binary operation... whichOne should either be
	// the string "left" or the string "right"
	public Expression getSubexpression (String whichOne) {

		// verify it is a valid expression type
		for (int i = 0; i < binaryTypes.length; i++) {
			if (myType.equals (binaryTypes[i])) {
				if (whichOne.equals ("left"))
					return leftSubexpression;
				else if (whichOne.equals ("right"))
					return rightSubexpression;
				else
					throw new RuntimeException ("whichOne must be left or right");
			}
		}

		// it is not valid, so throw an exception
		throw new RuntimeException ("you can't set the l/r subexpression of " +
				"an expression that is not binry!");
	}

	// this sets the left and the right subexpression
	public void setSubexpression (Expression left, Expression right) {

		// verify it is a valid expression type
		for (int i = 0; i < binaryTypes.length; i++) {
			if (myType.equals (binaryTypes[i])) {
				leftSubexpression = left;
				rightSubexpression = right;
				return;
			}
		}

		// it is not valid, so throw an exception
		throw new RuntimeException ("you can't get the l/r subexpression of " +
				"an expression that is not binry!");
	}
	
	/**
	 * Gets the return type of this expression.
	 * @return
	 */
	public String getReturnType(Map<String, String> tables,
			Map<String, TableData> catalog) {
		switch(myType) {
		
		// binary composite arithmetic operations have return type
		// of either Int or Float. Conversion to float should occur
		// if a floating point number is used in the calculation at all
		case "plus":
		case "minus":
		case "times":
		case "divided by":
			if (this.getSubexpression("left").getReturnType(tables, catalog).equals("Float"))
				return "Float";
			return this.getSubexpression("right").getReturnType(tables, catalog);
			
			// unary composite operations have return type
			// equal to return type of underlying operation
		case "unary minus":
		case "sum":
		case "avg":
			return this.getSubexpression().getReturnType(tables, catalog);
			
			// Boolean expressions are not valid return types for SQL, or are they??
			// Perhaps they are not for this project but this must be investigated further.
		case  "or":
		case "and":
		case "not":
		case "equals":
		case "greater than":
		case "less than":
			throw new RuntimeException("Return type of an expression should not be a boolean value.");
			
		case "identifier":
			CorrelatedAttribute ca = CorrelatedAttribute.parseCorrelatedAttribute(myValue);
			if (ca == null) {
				throw new RuntimeException("Attribute \"" + myValue + "\" is not a valid correlated attribute in getReturnType.");
			}

			String table = tables.get(ca.getCorrelation());
			if (table == null) {
				throw new RuntimeException("Attribute \"" + myValue + "\" has undefined correlation \"" + ca.getCorrelation() + "\" in getReturnType.");
			}

			AttInfo ai = catalog.get(table).getAttInfo(ca.getAttribute());
			if (ai == null) {
				throw new RuntimeException("Attribute \"" + myValue + "\" does not exist in table \"" + table + "\" in getReturnType.");
			}
			
			return ai.getDataType();
			
		case "literal string":
			return "Str";
		case "literal float":
			return "Float";
		case "literal int":
			return "Int";
			
		default:
			throw new RuntimeException("Expression of uknown type encountered: \"" + myType + "\".");
		}
	}
	
	/**
	 * Returns true if this expression is an expression which includes
	 * an aggregate function.
	 * @return true if this expression includes an aggregate function
	 */
	public boolean includesAggregateFunction() {
		if (myType == null)
			throw new RuntimeException("Called includesAggregateFunction on Expression with null myType.\n");
		
		if (myType.equals("sum") || myType.equals("avg"))
			return true;
		
		// If this type is a unary type then check its subtype
		for (String unaryType : Expression.unaryTypes) {
			if (myType.equals(unaryType))
				return getSubexpression().includesAggregateFunction();
		}
		
		// If this type is a binary type then check its subtypes.
		for (String binaryType : Expression.binaryTypes) {
			if (myType.equals(binaryType)) {
				if (getSubexpression("left").includesAggregateFunction())
					return true;
				return getSubexpression("right").includesAggregateFunction();
			}
		}
		
		// This is not a recursive type expression, so it cannot be an
		// aggregate.
		return false;
	}

	/**
	 * Checks that all grouping attributes are contained in the group by
	 * clause. Returns true if all grouping attributes are contained in
	 * the group by clause.
	 * @param groupBy
	 * @return
	 */
	public boolean checkGroupingAttributes(String groupBy) {
		
		// If this expression is an aggregate function then no
		// checking is necessary.
		if (myType.equals("sum") || myType.equals("avg"))
			return true;
		
		// Base case - value type identifier
		if (myType.equals("identifier")) {
			if (groupBy != null)
				return myValue.equals(groupBy);
			return true;
		}
		
		// Unary Type Case
		for (String unaryType : Expression.unaryTypes) {
			if (myType.equals(unaryType))
				return getSubexpression().checkGroupingAttributes(groupBy);
		}
		
		// Binary Type Case
		for (String binaryType : Expression.binaryTypes) {
			if (myType.equals(binaryType)) {
				if (!this.getSubexpression("left").checkGroupingAttributes(groupBy))
					return false;
				return this.getSubexpression("right").checkGroupingAttributes(groupBy);
			}
		}
		
		// This expression is some literal and thus
		// is valid.
		return true;
	}
	
	/**
	 * Returns true if all aggregate functions within this expression
	 * have valid input parameters, i.e. that they do not contain any
	 * aggregate functions in their input parameters.
	 * @return
	 */
	public boolean checkAggregateFunctionInput() {
		if (myType.equals("sum") || myType.equals("avg")) {
			return !getSubexpression().includesAggregateFunction();
		}
		
		// Check unary types
		for (String unaryType : Expression.unaryTypes) {
			if (myType.equals(unaryType))
				return getSubexpression().checkAggregateFunctionInput();
		}
		
		for (String binaryType : Expression.binaryTypes) {
			if (myType.equals(binaryType)) {
				if (!getSubexpression("left").checkAggregateFunctionInput())
					return false;
				return getSubexpression("right").checkAggregateFunctionInput();
			}
		}
		
		return true;
	}

	/**
	 * Validates that this expression contains no type mismatches.
	 * @param tables
	 * @param catalog
	 * @return
	 */
	public boolean checkType(Map<String, String> tables,
			Map<String, TableData> catalog) {
		
		if (DEBUG) System.out.println("Expression type " + myType + ".");
			
		switch(myType) {
		// plus can be of type numeric or string
		case "plus": 
			if (!checkTypeHelper(tables, catalog, TYPE_NUMERIC)) {
				if (DEBUG) System.out.println("Plus not TYPE_NUMERIC, trying TYPE_STRING.");
				return checkTypeHelper(tables, catalog, TYPE_STRING);
			}
			return true;

			// These three functions take only numeric parameters.
		case "minus":
		case "times":
		case "divided by":
		case "unary minus":
		case "sum":
		case "avg":
			return checkTypeHelper(tables, catalog, TYPE_NUMERIC);	
			
		case  "or":
		case "and":
		case "not":
		case "equals":
		case "greater than":
		case "less than":
			return checkTypeHelper(tables, catalog, TYPE_BOOLEAN);
			
			// literal types are validly typed
		case "literal string":
		case "literal float":
		case "literal int":
		case "identifier":
			return true;
			
		default:
			System.err.println("Expression \"" + myValue + "\" of unknown type " + myType + ".");
			return false;
		}
	}

	/**
	 * Returns true if this is a validly typed expression of type "type".
	 * @param tables
	 * @param catalog
	 * @param type
	 * @return
	 */
	private boolean checkTypeHelper(Map<String, String> tables,
			Map<String, TableData> catalog, int type) {
		
		if (DEBUG) System.out.println("Expression of type " + myType + ".");
		
		switch(myType) {
		// plus can be of type numeric or string
		case "plus":
			if (type != TYPE_NUMERIC && type != TYPE_STRING)
				return false;
			// The type of the result of + must be the same as
			// the type of its arguments
			if (!getSubexpression("left").checkTypeHelper(tables, catalog, type))
				return false;
			return getSubexpression("right").checkTypeHelper(tables, catalog, type);

		case "minus":
		case "times":
		case "divided by":
			// return type numeric
			if (type != TYPE_NUMERIC)
				return false;
			// parameters are type numeric
			if (!getSubexpression("left").checkTypeHelper(tables, catalog, type))
				return false;
			return getSubexpression("right").checkTypeHelper(tables, catalog, type);
				
		case "unary minus":
		case "sum":
		case "avg":
			// return type numeric
			if (type != TYPE_NUMERIC)
				return false;
			// parameter type numeric
			return getSubexpression().checkTypeHelper(tables, catalog, type);
			
		case  "or":
		case "and":
			// return type boolean
			if (type != TYPE_BOOLEAN)
				return false;
			// parameters type boolean
			if (!this.getSubexpression("left").checkTypeHelper(tables, catalog, type))
				return false;
			return getSubexpression("right").checkTypeHelper(tables, catalog, type);
			
		case "not":
			// return type boolean
			if (type != TYPE_BOOLEAN)
				return false;
			// parameter type boolean
			return getSubexpression().checkTypeHelper(tables, catalog, type);
			
		case "equals":
			// return type boolean
			if (type != TYPE_BOOLEAN)
				return false;
			// equals supports any data type for its left and right
			// but they must be the same data type
			for (int t = TYPE_MIN; t <= TYPE_MAX; t++) {
				if (this.getSubexpression("left").checkTypeHelper(tables, catalog, t) &&
						this.getSubexpression("right").checkTypeHelper(tables, catalog, t))
					return true;
			}
			return false;
			
		case "greater than":
		case "less than":
			// return type boolean
			if (type != TYPE_BOOLEAN)
				return false;
			// parameters type numeric
			/*
			if (!this.getSubexpression("left").checkTypeHelper(tables, catalog, TYPE_NUMERIC))
				return false;
			return this.getSubexpression("right").checkTypeHelper(tables, catalog, TYPE_NUMERIC);
			*/
			if (!this.getSubexpression("left").checkTypeHelper(tables, catalog, TYPE_NUMERIC)) {
				if (!this.getSubexpression("left").checkTypeHelper(tables, catalog, TYPE_STRING))
					return false;
				return this.getSubexpression("right").checkTypeHelper(tables, catalog, TYPE_STRING);
			}
			return this.getSubexpression("right").checkTypeHelper(tables, catalog, TYPE_NUMERIC);
			
		case "literal string":
			if (type != TYPE_STRING)
				return false;
			return true;
			
		case "literal float":
		case "literal int":
			if (type != TYPE_NUMERIC)
				return false;
			return true;
			
		case "identifier":
			// 
			CorrelatedAttribute ca = CorrelatedAttribute.parseCorrelatedAttribute(myValue);
			if (ca == null) {
				throw new RuntimeException("Attribute \"" + myValue + "\" is not a valid correlated attribute during type checking.");
			}

			String table = tables.get(ca.getCorrelation());
			if (table == null) {
				throw new RuntimeException("Attribute \"" + myValue + "\" has undefined correlation \"" + ca.getCorrelation() + "\" during type checking.");
			}

			AttInfo ai = catalog.get(table).getAttInfo(ca.getAttribute());
			if (ai == null) {
				throw new RuntimeException("Attribute \"" + myValue + "\" does not exist in table \"" + table + "\" during type checking.");
			}
			
			String dataType = ai.getDataType();
			switch (dataType) {
			case "Str":
				return (type == TYPE_STRING);
				
			case "Int":
			case "Float":
				return (type == TYPE_NUMERIC);
				
			default:
				throw new RuntimeException("Attribute \"" + myValue + "\" has invalid data type " + dataType + "\" in the catalog.");
			}
			
		default:
			System.err.println("Expression \"" + myValue + "\" of unknown type " + myType + ".");
			return false;
		}
	}
	
	/**
	 * Converts this expression to a String that can be executed
	 * by the provided execution engine code.
	 */
	public String oldToExecutionString() {
		
		switch(myType) {
		case "plus":
			return "(" + this.getSubexpression("left").toExecutionString() + " + " + this.getSubexpression("right").toExecutionString() + ")";
		case "minus":
			return "(" + this.getSubexpression("left").toExecutionString() + " - " + this.getSubexpression("right").toExecutionString() + ")";
		case "times":
			return "(" + this.getSubexpression("left").toExecutionString() + " * " + this.getSubexpression("right").toExecutionString() + ")";
		case "divided by":
			return "(" + this.getSubexpression("left").toExecutionString() + " / " + this.getSubexpression("right").toExecutionString() + ")";
		case "or":
			return "(" + this.getSubexpression("left").toExecutionString() + " || " + this.getSubexpression("right").toExecutionString() + ")";
		case "and":
			//return "(" + this.getSubexpression("left").toExecutionString() + " && " + this.getSubexpression("right").toExecutionString() + ")";
			return this.getSubexpression("left").toExecutionString() + " && " + this.getSubexpression("right").toExecutionString();
		case "not":
			return "(!" + this.getSubexpression().toExecutionString() + ")";
		case "literal string":
			//return "Str(\"" + myValue + "\")";
			return "Str(" + myValue + ")";
		case "literal float":
			return "Float (" + myValue + ")";
		case "literal int":
			return "Int (" + myValue + ")";
		case "identifier":
			return CorrelatedAttribute.parseCorrelatedAttribute(myValue).getAttribute();
			//return myValue;
		case "unary minus":
			return "(-" + this.getSubexpression().toExecutionString() + ")";
		case "sum":
			return this.getSubexpression().toExecutionString();
		case "avg":
			return this.getSubexpression().toExecutionString();
		case "equals":
			return "(" + this.getSubexpression("left").toExecutionString() + " == " + this.getSubexpression("right").toExecutionString() + ")";
		case "greater than":
			return "(" + this.getSubexpression("left").toExecutionString() + " > " + this.getSubexpression("right").toExecutionString() + ")";
		case "less than":
			return "(" + this.getSubexpression("left").toExecutionString() + " < " + this.getSubexpression("right").toExecutionString() + ")";
		}
		
		return null;
	}
	
	/**
	 * Converts this expression to a String that can be executed
	 * by the provided execution engine code.
	 */
	public String toExecutionString() {
		
		switch(myType) {
		case "plus":
			return "(" + this.getSubexpression("left").toExecutionString() + " + " + this.getSubexpression("right").toExecutionString() + ")";
		case "minus":
			return "(" + this.getSubexpression("left").toExecutionString() + " - " + this.getSubexpression("right").toExecutionString() + ")";
		case "times":
			return "(" + this.getSubexpression("left").toExecutionString() + " * " + this.getSubexpression("right").toExecutionString() + ")";
		case "divided by":
			return "(" + this.getSubexpression("left").toExecutionString() + " / " + this.getSubexpression("right").toExecutionString() + ")";
		case "or":
			return "(" + this.getSubexpression("left").toExecutionString() + " || " + this.getSubexpression("right").toExecutionString() + ")";
		case "and":
			//return "(" + this.getSubexpression("left").toExecutionString() + " && " + this.getSubexpression("right").toExecutionString() + ")";
			return this.getSubexpression("left").toExecutionString() + " && " + this.getSubexpression("right").toExecutionString();
		case "not":
			return "(!" + this.getSubexpression().toExecutionString() + ")";
		case "literal string":
			//return "Str(\"" + myValue + "\")";
			return "Str(" + myValue + ")";
		case "literal float":
			return "Float (" + myValue + ")";
		case "literal int":
			return "Int (" + myValue + ")";
		case "identifier":
			return myValue.replace('.', '_');
			//return CorrelatedAttribute.parseCorrelatedAttribute(myValue).getAttribute();
			//return myValue;
		case "unary minus":
			return "(-" + this.getSubexpression().toExecutionString() + ")";
		case "sum":
			return this.getSubexpression().toExecutionString();
		case "avg":
			return this.getSubexpression().toExecutionString();
		case "equals":
			return "(" + this.getSubexpression("left").toExecutionString() + " == " + this.getSubexpression("right").toExecutionString() + ")";
		case "greater than":
			return "(" + this.getSubexpression("left").toExecutionString() + " > " + this.getSubexpression("right").toExecutionString() + ")";
		case "less than":
			return "(" + this.getSubexpression("left").toExecutionString() + " < " + this.getSubexpression("right").toExecutionString() + ")";
		}
		
		return null;
	}

	public String toJoinString(ArrayList<Attribute> inAttsLeft, ArrayList<Attribute> inAttsRight)
	{

		switch(myType) {
		case "plus":
			return "(" + this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " + " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight) + ")";
		case "minus":
			return "(" + this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " - " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight) + ")";
		case "times":
			return "(" + this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " * " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight) + ")";
		case "divided by":
			return "(" + this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " / " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight) + ")";
		case "or":
			return "(" + this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " || " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight) + ")";
		case "and":
			//return "(" + this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " && " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight) + ")";
			return this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " && " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight);
		case "not":
			return "(!" + this.getSubexpression().toJoinString(inAttsLeft, inAttsRight) + ")";
		case "literal string":
			//return "Str(\"" + myValue + "\")";
			return "Str(" + myValue + ")";
		case "literal float":
			return "Float (" + myValue + ")";
		case "literal int":
			return "Int (" + myValue + ")";
		case "identifier":
			String joinName = myValue.replace('.', '_');
			for(Attribute a : inAttsLeft)
			{
				if(joinName.equals(a.getName()))
				{
					return "left." + joinName;
				}
			}
			return "right." + joinName;
			//return myValue.replace('.', '_');
			//return CorrelatedAttribute.parseCorrelatedAttribute(myValue).getAttribute();
			//return myValue;
		case "unary minus":
			return "(-" + this.getSubexpression().toJoinString(inAttsLeft, inAttsRight) + ")";
		case "sum":
			return this.getSubexpression().toJoinString(inAttsLeft, inAttsRight);
		case "avg":
			return this.getSubexpression().toJoinString(inAttsLeft, inAttsRight);
		case "equals":
			return "(" + this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " == " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight) + ")";
		case "greater than":
			return "(" + this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " > " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight) + ")";
		case "less than":
			return "(" + this.getSubexpression("left").toJoinString(inAttsLeft, inAttsRight) + " < " + this.getSubexpression("right").toJoinString(inAttsLeft, inAttsRight) + ")";
		}

		return null;
	}

	/**
	 * Takes an Expression and creates a list of all of the disjunctions
	 * within the expression.
	 * @return
	 */
	public ArrayList<Expression> toDisjunctions() {
		ArrayList<Expression> disjunctions;
		switch (myType) {
		case "and":
			disjunctions = this.getSubexpression("left").toDisjunctions();
			disjunctions.addAll(this.getSubexpression("right").toDisjunctions());
			return disjunctions;
		default:
			disjunctions = new ArrayList<Expression>();
			disjunctions.add(this);
			return disjunctions;
		}
	}
	
	/**
	 * Returns true if this expression references no tables except
	 * the one referred to by "correlation".
	 * @param correlation
	 * @return
	 */
	public boolean onlyReferencesTable(String correlation) {
		if (myType.equals("identifier")) {
			if (CorrelatedAttribute.parseCorrelatedAttribute(myValue).getCorrelation().equals(correlation))
				return true;
			return false;
		}
		
		for (String unaryType : unaryTypes) {
			if (myType.equals(unaryType))
				return this.getSubexpression().onlyReferencesTable(correlation);
		}
		
		for (String binaryType : binaryTypes) {
			if (myType.equals(binaryType)) {
				if (!this.getSubexpression("left").onlyReferencesTable(correlation))
					return false;
				return this.getSubexpression("right").onlyReferencesTable(correlation);
			}
		}
		
		return true;
	}
	
	/**
	 * Returns true if this correlation references the table
	 * referred to by correlation.
	 * @param correlation
	 * @return
	 */
	public boolean referencesTable(String correlation) {
		if (myType.equals("identifier")) {
			if (CorrelatedAttribute.parseCorrelatedAttribute(myValue).getCorrelation().equals(correlation))
				return true;
			return false;
		}
		
		for (String unaryType : unaryTypes) {
			if (myType.equals(unaryType))
				return this.getSubexpression().referencesTable(correlation);
		}
		
		for (String binaryType : binaryTypes) {
			if (myType.equals(binaryType)) {
				if (this.getSubexpression("left").referencesTable(correlation))
					return true;
				return this.getSubexpression("right").referencesTable(correlation);
			}
		}
		
		return false;
	}

	/**
	 * Creates a single conjunctive expression containing all disjunctions
	 * in the provided arraylist of Expression.
	 * @param disjunctions
	 * @return
	 */
	public static Expression reJunct(ArrayList<Expression> disjunctions) {
		if (disjunctions == null || disjunctions.isEmpty())
			return null;
		
		int n = disjunctions.size();
		if (n == 1) {
			return disjunctions.get(0);
		}

		Expression and = new Expression("and");
		and.setSubexpression(disjunctions.get(0), disjunctions.get(1));
		for (int i = 2; i < disjunctions.size(); i++) {
			Expression newAnd = new Expression("and");
			newAnd.setSubexpression(and, disjunctions.get(i));
			and = newAnd;
		}
		return and;
	}

	/**
	 * Adds all identifiers into the list of projected attributes.
	 * @param projectedAtts
	 */
	public void computeProjectedAtts(ArrayList<Expression> projectedAtts) {
		if (myType.equals("identifier")) {
			projectedAtts.add(this);
			return;
		}
		
		for (String unaryType : unaryTypes)
			if (myType.equals(unaryType)) {
				getSubexpression().computeProjectedAtts(projectedAtts);
				return;
			}
		
		for (String binaryType : binaryTypes) {
			if (myType.equals(binaryType)) {
				this.getSubexpression("left").computeProjectedAtts(projectedAtts);
				this.getSubexpression("right").computeProjectedAtts(projectedAtts);
				return;
			}
		}
	}
	
	/**
	 * Computes the filter factor for an expression. Whenever a filter factor is computed based on a table attribute such that
	 * the attribute's cardinality in the output is known to now be different, that attribute is added to the updated temporary
	 * catalog which is merged with tempCatalog after the entire filter factor computation completes.
	 * @param from
	 * @param catalog
	 * @param tempCatalog
	 * @return
	 */
	public double computeFilterFactor(Map<String, String> from, Map<String, TableData> catalog, Map<String, TableData> tempCatalog,
			Map<String, TableData> updatedTempCatalog)
	{
		
		// For now only support less than, greater than, equals, and, and or
		// otherwise it's not really a predicate. I'm not sure that I built in
		// this semantic check.
		switch(myType)
		{
			case "less than":
			case "greater than":
				// Make these recursive calls to ensure that the temporary catalog gets updated since this affects
				// future cost estimations. The updating of the temporary catalog really should be abstracted out
				// from the estimateCardinality method call so that I don't have to do this bad call.
				// TODO: fix method of updating catalog at some point
				this.getSubexpression("left").estimateCardinality(from, catalog, tempCatalog, updatedTempCatalog);
				this.getSubexpression("right").estimateCardinality(from, catalog, tempCatalog, updatedTempCatalog);
				return 1.0 / 3.0;
			case "and":
				return this.getSubexpression("left").computeFilterFactor(from, catalog, tempCatalog, updatedTempCatalog) *
						this.getSubexpression("right").computeFilterFactor(from, catalog, tempCatalog, updatedTempCatalog);
			case "or":
				double leftFilter = this.getSubexpression("left").computeFilterFactor(from, catalog, tempCatalog, updatedTempCatalog);
				double rightFilter = this.getSubexpression("right").computeFilterFactor(from, catalog, tempCatalog, updatedTempCatalog);
				return 1.0 - ((1.0 - leftFilter) * (1.0 - rightFilter));
			case "equals":
				// The best way to cost an equals expression depends on what is being compared.
				
				// identifier = value
				// value = identifier
				// f(i) = value                  => filterFactor = 1 / card(i_1)
				// f(i_1, i_2) = value           => number of possible values upper bounded at card(i_1) * card(i_2)
				// f(i_1, i_2, ..., i_n) = value => number of possible values upper bounded at PRODUCT_{k = 1}^n card(i_k)
				
				// use filter factor 1 / PROD{k=1,2,...,n} card(i_k)
				// This estimation might underestimate the filter factor
				
				long leftCard = this.getSubexpression("left").estimateCardinality(from, catalog, tempCatalog, updatedTempCatalog);
				long rightCard = this.getSubexpression("right").estimateCardinality(from, catalog, tempCatalog, updatedTempCatalog);
				if(leftCard == 0 || rightCard == 0)
				{
					if(DBConfig.DEBUG)
					{
						System.out.println("Cardinatlity of 0 for expression " + this.myValue + " of type " + this.myType + ".");
					}
					return 0.0;
				}
				
				return 1.0 / (leftCard * rightCard);
			case "not":
				return 1.0 - this.getSubexpression().computeFilterFactor(from, catalog, tempCatalog, updatedTempCatalog);
			default:
				throw new RuntimeException("Unexpected Expression of type " + myType + "found in where clause.");
		}
		
	}

	/**
	 * Helper function for equals case to compute the cardinality of an expression.
	 * @param from 
	 * @param catalog
	 * @param tempCatalog 
	 * @return
	 */
	private long estimateCardinality(Map<String, String> from, Map<String, TableData> catalog, Map<String, TableData> tempCatalog,
			Map<String, TableData> updatedTempCatalog)
	{
		if(this.myType == "identifier")
		{
			if(from == null)
			{
				return 1;
			}
			
			// look up this attribute's cardinality in the catalog and return it.
			// perhaps this look up should be encapsulated in the catalog - this would require an enhanced catalog class
			// This method is only called when an attribute is being filtered. Therefore once an attribute has been
			// looked up, we know that there is only one possible value for it given our assumptions that when an attribute
			// is looked up, a single unique value for it will be used. When this occurs the data in the catalog needs to
			// be updated. To manage this, we will create a temporary TableData entry in the catalog called TEMP.tablename
			
			CorrelatedAttribute ca = CorrelatedAttribute.parseCorrelatedAttribute(myValue);
			String correlation = ca.getCorrelation();
			String attribute = ca.getAttribute();
			String table = from.get(correlation);
			
			// When doing a join, if the leftFrom is passed and this identifier is in the rightFrom
			// then the table may not be found.
			if(table == null)
			{
				return 1;
			}
			
			TableData td = tempCatalog.get(table);
			if(td == null)
			{
				td = catalog.get(table).clone();
				DBUtils.mergeCatalogTableData(updatedTempCatalog, table, td);
				//updatedTempCatalog.put(table, td);
			}
			if(td == null)
			{
				throw new RuntimeException("Unexpectedly table " + table + " is not present in catalog!");
			}
			
			// Set the temporary table information for this particular attribute to 1 since we are filtering
			// for a particular value.
			AttInfo ai = td.getAttInfo(attribute);
			long numDistinctVals = ai.getNumDistinctVals();
			ai.setNumDistinctVals(1);
			DBUtils.mergeCatalogTableData(updatedTempCatalog, table, td);
			return numDistinctVals;
		}
		
		for(String unaryType : unaryTypes)
		{
			if(myType.equals(unaryType))
			{
				return this.getSubexpression().estimateCardinality(from, catalog, tempCatalog, updatedTempCatalog);
			}
		}
		
		for(String binaryType : binaryTypes)
		{
			if(myType.equals(binaryType))
			{
				long leftCard = this.getSubexpression("left").estimateCardinality(from, catalog, tempCatalog, updatedTempCatalog);
				long rightCard = this.getSubexpression("right").estimateCardinality(from, catalog, tempCatalog, updatedTempCatalog);
				return leftCard * rightCard;
			}
		}
		
		return 1;
	}

//	public double computeFilterFactor(Map<String, String> leftFrom,
//			Map<String, String> rightFrom, Map<String, TableData> catalog,
//			Map<String, TableData> leftTempCatalog,
//			Map<String, TableData> rightTempCatalog,
//			Map<String, TableData> updatedTempCatalog)
//	{
//		// For now only support less than, greater than, equals, and, and or
//		// otherwise it's not really a predicate. I'm not sure that I built in
//		// this semantic check.
//		switch (myType)
//		{
//			case "less than":
//			case "greater than":
//				return 1.0 / 3.0;
//			case "and":
//				return this.getSubexpression("left").computeFilterFactor(leftFrom, rightFrom, catalog, leftTempCatalog, rightTempCatalog, updatedTempCatalog)
//						* this.getSubexpression("right").computeFilterFactor(leftFrom, rightFrom, catalog, leftTempCatalog, rightTempCatalog, updatedTempCatalog);
//			case "or":
//				double leftFilter = this.getSubexpression("left").computeFilterFactor(leftFrom, rightFrom, catalog, leftTempCatalog, rightTempCatalog, updatedTempCatalog);
//				double rightFilter = this.getSubexpression("right").computeFilterFactor(leftFrom, rightFrom, catalog, leftTempCatalog, rightTempCatalog, updatedTempCatalog);
//				return 1.0 - ((1.0 - leftFilter) * (1.0 - rightFilter));
//			case "equals":
//				// The best way to cost an equals expression depends on what is
//				// being compared.
//
//				// identifier = value
//				// value = identifier
//				// f(i) = value => filterFactor = 1 / card(i_1)
//				// f(i_1, i_2) = value => number of possible values upper
//				// bounded at card(i_1) * card(i_2)
//				// f(i_1, i_2, ..., i_n) = value => number of possible values
//				// upper bounded at PRODUCT_{k = 1}^n card(i_k)
//
//				// use filter factor 1 / PROD{k=1,2,...,n} card(i_k)
//				// This estimation might underestimate the filter factor
//
//				long leftLeftCard = 1;
//				long leftRightCard = 1;
//				long rightLeftCard = 1;
//				long rightRightCard = 1;
//				
////				if(leftFrom != null)
////				{
//					leftLeftCard = this.getSubexpression("left").estimateCardinality(leftFrom, catalog, leftTempCatalog, updatedTempCatalog);
//					rightLeftCard = this.getSubexpression("right").estimateCardinality(leftFrom, catalog, leftTempCatalog, updatedTempCatalog);
////				}
//				
////				if(rightFrom != null)
////				{
//					leftRightCard = this.getSubexpression("left").estimateCardinality(rightFrom, catalog, rightTempCatalog, updatedTempCatalog);
//					rightRightCard = this.getSubexpression("right").estimateCardinality(rightFrom, catalog, rightTempCatalog, updatedTempCatalog);
////				}
//				
//				// Note that in the other version of cost left and right simply refer to the left and right side of
//				// the AND. Here they refer to the left tables in the join and the right tables in the join.
//				// Left tables in join card
//				long leftCard = leftLeftCard * rightLeftCard;
//				// Right tables in join card
//				long rightCard = leftRightCard * rightRightCard;
//				
//				if (leftCard == 0 || rightCard == 0)
//				{
//					if (Interpreter.DEBUG)
//					{
//						System.out.println("Cardinatlity of 0 for expression " + this.myValue + " of type " + this.myType + ".");
//					}
//					return 0.0;
//				}
//
//				return 1.0 * Math.min(leftCard, rightCard) / (leftCard * rightCard);
//
//			default:
//				throw new RuntimeException("Unexpected Expression of type "	+ myType + "found in where clause.");
//		}
//	}
	
	public ArrayList<String> getCorrelations()
	{
		if(myType.equals("identifier"))
		{
			ArrayList<String> correlations = new ArrayList<String>();
			CorrelatedAttribute ca = CorrelatedAttribute.parseCorrelatedAttribute(myValue);
			correlations.add(ca.getCorrelation());
			return correlations;
		}
		else if(isUnaryType())
		{
			return this.getSubexpression().getCorrelations();
		}
		else if(isBinaryType())
		{
			ArrayList<String> leftCorrelations = this.getSubexpression("left").getCorrelations();
			ArrayList<String> rightCorrelations = this.getSubexpression("right").getCorrelations();
			if(leftCorrelations == null)
			{
				return rightCorrelations;
			}
			else
			{
				leftCorrelations.addAll(rightCorrelations);
				return leftCorrelations;
			}
		}
		
		return null;
	}
	
	public Set<String> getSetOfCorrelations()
	{
		if(myType.equals("identifier"))
		{
			Set<String> allCorrelations = new HashSet<String>();
			CorrelatedAttribute ca = CorrelatedAttribute.parseCorrelatedAttribute(myValue);
			allCorrelations.add(ca.getCorrelation());
			return allCorrelations;
		}
		else if(this.isUnaryType())
		{
			return this.getSubexpression().getSetOfCorrelations();
		}
		else if(this.isBinaryType())
		{
			Set<String> leftCorrelations = this.getSubexpression("left").getSetOfCorrelations();
			Set<String> rightCorrelations = this.getSubexpression("right").getSetOfCorrelations();
			if(leftCorrelations == null)
			{
				return rightCorrelations;
			}
			else if(rightCorrelations == null)
			{
				return leftCorrelations;
			}
			else
			{
				leftCorrelations.addAll(rightCorrelations);
				return leftCorrelations;
			}
		}
		else
		{
			return null;
		}
	}
	
	private boolean isBinaryType()
	{
		for(String binaryType : Expression.binaryTypes)
		{
			if(myType.equals(binaryType))
			{
				return true;
			}
		}
		return false;
	}

	private boolean isUnaryType()
	{
		for(String unaryType : Expression.unaryTypes)
		{
			if(myType.equals(unaryType))
			{
				return true;
			}
		}
		return false;
	}

	public String toString()
	{
		return "[" + toExecutionString() + "]";
		//return "[" + myType + ":" + myValue + "]";
	}

	public ArrayList<Expression> getIdentifiers()
	{
		if(myType.equals("identifier"))
		{
			ArrayList<Expression> a = new ArrayList<Expression>(1);
			a.add(this);
			return a;
		}
		else if(this.isUnaryType())
		{
			return this.getSubexpression().getIdentifiers();
		}
		else if(this.isBinaryType())
		{
			ArrayList<Expression> left = this.getSubexpression("left").getIdentifiers();
			ArrayList<Expression> right = this.getSubexpression("right").getIdentifiers();
			if(left == null)
			{
				return right;
			}
			else if(right == null)
			{
				return left;
			}
			else
			{
				left.addAll(right);
				return left;
			}
		}
		
		return null;
	}
	
	public int hashCode()
	{
		return this.myValue.hashCode();
	}
	
	public boolean equals(Object o)
	{
		if(o == null)
		{
			return false;
		}
		else if(this == o)
		{
			return true;
		}
		
		if(!(o instanceof Expression))
		{
			return false;
		}
		Expression e = (Expression) o;
		
		if(myType.equals(e.myType) && myValue.equals(myValue))
		{
			if(this.isUnaryType())
			{
				return this.getSubexpression().equals(e.getSubexpression());
			}
			else if(this.isBinaryType())
			{
				return this.getSubexpression("left").equals(e.getSubexpression("left")) &&
						this.getSubexpression("right").equals(e.getSubexpression("right"));
			}
			else
			{
				return true;
			}
		}
		return false;
	}
}


